# Definition for binary tree with next pointer.
class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

class Solution:
	# @param root, a tree link node
	# @return nothing
	def connect(self, root):
		if root and root.left:
			root.left.next = root.right
		else:
			return
		if root.left.right:
			ll = root.left
			rr = root.right
			ll.next = rr
			while ll.right:
				ll = ll.right
				rr = rr.left
				ll.next = rr
			self.connect(root.left)
			self.connect(root.right)

if __name__ == '__main__':
	r = TreeLinkNode(0)
	a1 = TreeLinkNode(1)
	a2 = TreeLinkNode(2)
	a3 = TreeLinkNode(3)
	a4 = TreeLinkNode(4)
	a5 = TreeLinkNode(5)
	a6 = TreeLinkNode(6)
	a7 = TreeLinkNode(7)
	a8 = TreeLinkNode(8)
	a9 = TreeLinkNode(9)
	a10 = TreeLinkNode(10)
	a11 = TreeLinkNode(11)
	a12 = TreeLinkNode(12)
	a13 = TreeLinkNode(13)
	a14 = TreeLinkNode(14)


	#r.left, r.right = a1, a2
	a1.left, a1.right= a3, a4
	a2.left, a2.right = a5, a6
	a3.left, a3.right = a7, a8
	a4.left, a4.right = a9, a10
	a5.left, a5.right = a11, a12
	a6.left, a6.right = a13, a14 

	so = Solution()
	so.connect(r)

	import sys
	for a in [r, a1, a3, a7]:
		t = a
		while t:
			sys.stdout.write(str(t.val) + ' ')
			t = t.next
		sys.stdout.write('\n')